
#include <iostream>
#include <iomanip>
#include <vector>
#include <time.h>

using namespace std;

//#define USE_SHORT 

#if defined(USE_SHORT)

// for short
typedef unsigned short        small_unit;
typedef unsigned long        big_unit;

const short MAX_NUM_IN_SMALL_UNIT    = 10000;
const short MAX_WIDTH_IN_SMALL_UNIT    = 4;

#else

// for long
typedef unsigned long        small_unit;
typedef unsigned long long    big_unit;

const long MAX_NUM_IN_SMALL_UNIT        = 1000000000L;
const short MAX_WIDTH_IN_SMALL_UNIT        = 9;

#endif

void multiply(vector<small_unit>& vec, small_unit num)
{
    big_unit multiResult = 0;
    small_unit highResult = 0;

    for(unsigned int i = 0; i < vec.size(); ++i)
    {
        multiResult = (big_unit)vec[i] * num;
        multiResult += highResult;

        vec[i] = multiResult % MAX_NUM_IN_SMALL_UNIT;
        highResult = (small_unit) (multiResult / MAX_NUM_IN_SMALL_UNIT);
    }

    if(highResult > 0)
    {
        vec.push_back(highResult);
    }
}

void printFull(vector<small_unit>& vec, small_unit num)
{
    cout<<num<<"! = ";

    cout<<vec[vec.size() - 1];

    for(int i = vec.size() - 2; i >= 0; --i)
    {
        // TODO set format for all output
        cout<<setfill('0')<<setw(MAX_WIDTH_IN_SMALL_UNIT);
        cout<<vec[i];
    }

    cout<<endl;
}

void printShort(vector<small_unit>& vec, small_unit num)
{
    cout<<num<<"! = ";
    small_unit firstVal = vec[vec.size() - 1];

    short n = 1;
    big_unit div = 10;
    while((firstVal / div) > 0)
    {
        ++n;
        div *= 10;
    }    

    --n;
    div /= 10;
    
    float val = ((float)firstVal) / div;
    long e = n + (vec.size() - 1) * MAX_WIDTH_IN_SMALL_UNIT;
    cout<<val<<"e+"<<e<<endl;
}

int main(int argc, char* argv[])
{
    small_unit num = 0;

    cout<<"Please input a number: ";
    cin>>num;

    vector<small_unit> vec;
    vec.push_back(1);

    time_t start, end;
    double diffTime = 0;

    time(&start);

    for(small_unit i = 2; i <= num; ++i)
    {
        multiply(vec, i);
    }

    time(&end);
    diffTime = difftime(end, start);

    //printFull(vec, num);
    printShort(vec, num);

    cout<<"Time used: "<<diffTime<<"s."<<endl;

    return 0;
}

